44. Wildcard Matching

Similar Question

Solution Tips

方案一: 动态规划

Loading Question... - 力扣（LeetCode）

var isMatch = function(s, p) {
    // if (s.length === 0 && p.)
    // 感觉也不是很难呀, 就一个个字符匹配不就好了?
    // 难点好像在*号, 可以匹配任意的字符序列
    // 假如出现了星号, 必须把其余存在的字符也匹配上才行
    const dp = Array.from({ length: s.length + 1 }, () => Array.from({ length: p.length + 1 }, () => false));
    // 定义 dp[i][j] 为 s 的前 i - 1 个字符能有使用 p 的前 j - 1 个字符匹配
    // 空串必定可以匹配空串
    dp[0][0] = true;
    // 这个初始化有点难想
    for (let i = 1; i <= p.length; ++i) {
        if (p[i - 1] == '*') {
            dp[0][i] = true;
        } else {
            break;
        }
    }

    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= p.length; j++) {
            if (s[i - 1] === p[j - 1]) {
                // 两个字符完全相等, s 仅有小写字母组成, 前一个序列能匹配就可以匹配
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (p[j - 1] === '?') {
                // 可以匹配任何字符, 所以可以匹配上
                dp[i][j] = dp[i - 1][j - 1]
            }
            else if (p[j - 1] === '*') {
                // 遍历一下 dp[0-i][j - 1], 只要之前有一个为 true 的, 都可以用 * 号从它开始匹配上
                dp[i][j] = false;
                if (j === 1) {
                    // 特殊情况, 如果 * 号在第一位, 就可以全部匹配成功
                    dp[i][j] = true
                }
                for (let k = 0; k <= i; k++) {
                    if (dp[k][j - 1]) {
                        dp[i][j] = true;
                    }
                }
            }
        }
    }

    return dp[s.length][p.length]
};

方案二: 贪心算法

Loading Question... - 力扣（LeetCode）